#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/18
# @Author   :Changshu
# @File     :Exercise_590.py
# 590. N叉树的后序遍历
# 给定一个 N 叉树，返回其节点值的后序遍历。

# Definition for a Node.
class Node:
	def __init__(self, val=None, children=None):
		self.val = val
		self.children = children


class Solution:
	'''法一：递归
	def postorder(self, root: 'Node') -> list:
		res=[]
		def helper(root:Node):
			if not root:
				return
			for node in root.children:
				helper(node)
			res.append(root.val)
		helper(root)
		return res
	'''

	'''法二：迭代'''
	def postorder(self, root: 'Node') -> list:
		res=[]
		if not root:
			return res
		visited=[root]
		while len(visited):
			node=visited.pop(0)
			res.insert(0,node.val)
			for n in node.children:
				visited.insert(0,n)
		return res

if __name__ == '__main__':
	root=Node(1,[])
	node2_1=Node(3,[])
	node2_2 = Node(2,[])
	node2_3 = Node(4,[])
	node3_1 = Node(5,[])
	node3_2 = Node(6,[])
	root.children.append(node2_1)
	root.children.append(node2_2)
	root.children.append(node2_3)
	node2_1.children.append(node3_1)
	node2_1.children.append(node3_2)


	solution=Solution()
	print(solution.postorder(root))
